import json
import os
import sys

from fastapi import HTTPException, status

from app.core.handlers.response import SuccessResponse

cache_dir = os.path.join(os.path.dirname(__file__), "cache")
os.makedirs(cache_dir, exist_ok=True)
cache_file = os.path.join(cache_dir, "egg_drop_cache.json")


def _load_cache(with_cache: bool):
    """加载缓存数据"""
    if with_cache and os.path.exists(cache_file):
        with open(cache_file) as f:
            cache = json.load(f)
        cached_eggs, cached_floors = cache["eggs"], cache["floors"]
        dp = cache["dp"]
        return cached_eggs, cached_floors, dp, cache
    else:
        return 0, 0, None, None


def _initialize_cache(eggs: int, floors: int):
    """初始化缓存"""
    dp = [[0] * (floors + 1) for _ in range(eggs + 1)]
    cache = {"eggs": eggs, "floors": floors, "dp": dp}
    return cache


def _can_use_cache(eggs: int, floors: int, cached_eggs: int, cached_floors: int):
    """检查是否可以使用缓存"""
    return eggs <= cached_eggs and floors <= cached_floors


def _calculate_dp_value(i: int, j: int, new_dp):
    """计算dp[i][j]的值"""
    # 如果没有鸡蛋，则不需要次数
    if i == 0:
        return 0
    # 如果没有楼层，则不需要次数
    elif j == 0:
        return 0
    # 如果只有一个鸡蛋，则需要的次数为楼层数
    elif i == 1:
        return j
    # 如果只有一个楼层，则需要的次数为1
    elif j == 1:
        return 1
    else:
        # 需要计算最小次数
        res = sys.maxsize
        # 从1到楼层数中，找到最小的次数
        for k in range(1, j + 1):
            # 从k层楼扔鸡蛋分为2种情况
            # 1 鸡蛋没有碎，从k楼上扔鸡蛋，还有i个鸡蛋，剩余j-k层楼
            k_up = new_dp[i][j - k]
            # 2 鸡蛋碎了，从k楼上扔鸡蛋，还有i-1个鸡蛋，剩余k-1层楼
            k_down = new_dp[i - 1][k - 1]
            # 取最小次数
            res = min(max(k_up, k_down) + 1, res)
        return res


# 生成动态规划数组
def generate_critical_floor_dp(eggs: int, floors: int, with_cache: bool = True):
    # 读取缓存文件
    cached_eggs, cached_floors, dp, cache = _load_cache(with_cache)

    if cache is None:
        cached_eggs, cached_floors = 0, 0
        cache = _initialize_cache(eggs, floors)
        dp = cache["dp"]

    # 如果查询数据命中缓存，则直接返回缓存数据
    if _can_use_cache(eggs, floors, cached_eggs, cached_floors):
        return cache

    # 构建新缓存
    new_dp = [
        [0] * (max(floors, cached_floors) + 1)
        for _ in range(max(eggs, cached_eggs) + 1)
    ]

    for i in range(max(eggs, cached_eggs) + 1):
        for j in range(max(floors, cached_floors) + 1):
            # 如果已经缓存过，则从缓存中读取数据
            if i <= cached_eggs and j <= cached_floors:
                new_dp[i][j] = dp[i][j]
            else:
                new_dp[i][j] = _calculate_dp_value(i, j, new_dp)

    return {
        "eggs": max(eggs, cached_eggs),
        "floors": max(floors, cached_floors),
        "dp": new_dp,
    }


# 最多需要的次数
def find_critical_count(eggs: int, floors: int, with_cache: bool = True):
    try:
        dp_result = generate_critical_floor_dp(eggs, floors, with_cache)
        new_dp = dp_result.get("dp")

        with open(cache_file, "w") as f:
            json.dump(dp_result, f)

        return SuccessResponse(message="计算成功", data=new_dp[eggs][floors])
    except Exception as e:
        raise HTTPException(
            status_code=status.HTTP_500_INTERNAL_SERVER_ERROR,
            detail=f"发生错误: {str(e)}",
        )


# 最少次数需要的蛋数量
def find_critical_eggs(floors: int, with_cache: bool = True):
    try:
        dp_result = generate_critical_floor_dp(floors, floors, with_cache)
        new_dp = dp_result.get("dp")

        with open(cache_file, "w") as f:
            json.dump(dp_result, f)

        egg_numbers = 0
        for i in range(1, floors + 1):
            if new_dp[i][floors] != new_dp[i - 1][floors]:
                egg_numbers = i

        return SuccessResponse(message="计算成功", data=egg_numbers)
    except Exception as e:
        raise HTTPException(
            status_code=status.HTTP_500_INTERNAL_SERVER_ERROR,
            detail=f"发生错误: {str(e)}",
        )


if __name__ == "__main__":
    print(find_critical_count(2, 100, False))
    print(find_critical_eggs(100))
